package utils;

import java.util.ArrayList;
import java.util.List;

import domain.Mesa;


public class BacktrackingRepartoMesas {
	
static int N = 31; //la posición 0 no se usa por comodidad 
static int[]capacidadesMesas = new int[N];
static int cantidadTotalComensales;
static int[] mesas = new int[N];
static int[] mesasSolucion = new int[N];;
static int numMesasMejorSolucion = Integer.MAX_VALUE;
	

	static void repartirMesas(int comensales, int numMesas) {
		for (int i = 0; i < N; i++) {
			// Si el estado es posible, es decir, podemos usar la mesa capacidadesMesas[i]
			if (comensales + capacidadesMesas[i] <= cantidadTotalComensales) {
				// Anotar estado
				comensales = comensales + capacidadesMesas[i];
				mesas[i]++;
				numMesas++;

				// Si no es solucion final
				if (comensales < cantidadTotalComensales) {
					// Ensayar nuevo estado
					repartirMesas(comensales, numMesas);
				} else {
					// Comprobar si es la mejor solucion
					if (numMesas < numMesasMejorSolucion) {
						numMesasMejorSolucion = numMesas;
						System.arraycopy(mesas, 0, mesasSolucion, 0, N);
					}
				}

				// Borrar anotacion
				numMesas--;
				mesas[i]--;
				comensales = comensales - capacidadesMesas[i];
			}
		}
	}


	//Debe recibir las mesas ordenadas de mayor a menor
	public static  List<Mesa> distribuirMesas(List<Mesa> mesasRestaurante, Integer numComensales){
		List<Mesa> mesasReserva = new ArrayList<Mesa>();
		cantidadTotalComensales = numComensales;
		
		iniciarMesas(mesasRestaurante);
		
		repartirMesas(0, 0);
		
		for (int i = 0; i < mesasSolucion.length; i++) {
			int numMesasCapacidadI = mesasSolucion[i];
			if(numMesasCapacidadI != 0){
				int indice = buscarMesaPorCapacidad(mesasRestaurante, i);
				mesasReserva.add(mesasRestaurante.get(indice));
			}
		}
		
		return mesasReserva;
		
		
	}


	private static void iniciarMesas(List<Mesa> mesasRestaurante) {
		for (int i = 0; i < capacidadesMesas.length; i++) {
			capacidadesMesas[i] = 0;
			mesas[i] = 0;
			mesasSolucion[i] = 0;
			numMesasMejorSolucion = Integer.MAX_VALUE;
		}
		for (Mesa mesa : mesasRestaurante) {
			int i = mesa.getCapacidad().intValue();
			capacidadesMesas[i]++;

		}
		
	}
	
	
	private static int buscarMesaPorCapacidad(List<Mesa> mesasRestaurante, int capacidad){
		for(int i = 0; i<= mesasRestaurante.size(); i++){
			Mesa mesa = mesasRestaurante.get(i);
			if(mesa.getCapacidad().intValue() == capacidad)
				return i;
		}
		
		return 0;
	}

}
